package com.mgq.algorithm.link;

import java.util.Stack;

/**
 * @author MaGuangQi
 * 删除链表的倒数第k个元素,并返回链表的header
 * @date 2021-12-31 14:11
 **/
public class RemoveNthFromEnd_19 {
    /**
     * 思路:也是使用的双指针.p1先走k步,然后p2再走.
     * 最后p1为空时,p2指向的就是倒数第k个元素
     * 这个题最难的是处理边界问题.[1,2] 2 此时需要删除头.容易空指针
     * [1] 1 需要完全删除
     * 为了简化问题,引入dummy节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p1=head;
        ListNode dummy = new ListNode(-1,head);
        ListNode p2=dummy;
        //p1先走n步
        for (int i = 0; i < n; i++) {
            p1=p1.next;
        }
        while (p1 != null) {
            p2=p2.next;
            p1=p1.next;
        }
        //引入dummy节点,直接简化了问题.此时p2恰好在被删除节点的前面.直接指向下下节点即可
        p2.next=p2.next.next;
        return dummy.next;
    }

    /**
     * 使用栈来解决
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        ListNode cur=dummy;
        Stack<ListNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur=cur.next;
        }
        //先让倒数n+1的节点出栈
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        ListNode pre = stack.peek();
        pre.next=pre.next.next;
        return dummy.next;
    }
}
